package 双周赛;

import java.util.Arrays;
import java.util.List;

/**
 *
 */
public class 第111场双周赛 {

    public static void main(String[] args) {

        System.out.println(canMakeSubsequence("abc", "ad"));

        System.out.println(minimumOperations(Arrays.asList(1, 3)));

    }

    /**
     * 枚举
     */
    public int countPairs(List<Integer> nums, int target) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums.get(i) + nums.get(j) < target) {
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 贪心+双指针
     */
    public static boolean canMakeSubsequence(String str1, String str2) {
        int idx1 = 0, idx2 = 0;
        while (idx1 < str1.length() && idx2 < str2.length()) {
            while (idx1 < str1.length() &&
                    str1.charAt(idx1) != str2.charAt(idx2) &&
                    str1.charAt(idx1) - str2.charAt(idx2) != -1 &&
                    str1.charAt(idx1) - str2.charAt(idx2) != 25) {
                idx1++;
            }

            if (idx1 == str1.length()) {
                break;
            }
            idx1++;
            idx2++;
        }
        return idx2 == str2.length() ? true : false;
    }

    /**
     * 前缀和+枚举+分类讨论
     * 一个有 5 中情况
     * 1，全部是 1 或者 2 或者 3
     * 2，前面是 1 中间是 2 后面是 3
     * 3，前面是 1 后面是 2
     * 4，前面是 1 后面是 3
     * 5，前面是 2 后面是 3
     */
    public static int minimumOperations(List<Integer> nums) {
        int[][] prefixSum = new int[4][nums.size() + 1];
        for (int i = 0; i < nums.size(); i++) {
            prefixSum[1][i + 1] = prefixSum[1][i];
            prefixSum[2][i + 1] = prefixSum[2][i];
            prefixSum[3][i + 1] = prefixSum[3][i];
            int[] preSum = prefixSum[nums.get(i)];
            preSum[i + 1] = preSum[i] + 1;
        }

        int n = nums.size();
        int ans = Math.min(n - prefixSum[3][n], Math.min(n - prefixSum[1][n], n - prefixSum[2][n]));

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // [0,i]=1 (i,j]=2 (j,n)=3
                int operate1 = i + 1 - prefixSum[1][i + 1] +
                        j - i - (prefixSum[2][j + 1] - prefixSum[2][i + 1])
                        + n - j - 1 - (prefixSum[3][n] - prefixSum[3][j + 1]);
                ans = Math.min(ans, operate1);
            }
            // [0,i]=2 (i,n)=3
            int operate2 = i + 1 - prefixSum[2][i + 1]
                    + n - i - 1 - (prefixSum[3][n] - prefixSum[3][i + 1]);
            ans = Math.min(ans, operate2);
            // [0,i]=1 (i,n)=3
            int operate3 = i + 1 - prefixSum[1][i + 1] +
                    n - i - 1 - (prefixSum[3][n] - prefixSum[3][i + 1]);
            ans = Math.min(ans, operate3);
        }

        return ans;
    }

}
